

def NBITS(N):
    n1 = hex(N)[:]
    return len(n1)*4

def find_pq(d0,e,N):
    X = var('X')
    PR.<x> = PolynomialRing(Zmod(N))

    print '[ ] Thinking...'
    for k in xrange(1, e+1):
        results = solve_mod([e * d0 * X - k * X * (N - X + 1) + k * N == X], 2 ** known_bits)

        for m in results:
            f = x * 2 ** known_bits + ZZ(m[0])
            f = f.monic()
            roots = f.small_roots(X = 2 ** (NBITS(N) / 2 - known_bits), beta=0.3)
            
            if roots:
                x0 = roots[0]
                p = gcd(2 ** known_bits * x0 + ZZ(m[0]), N)
                print '[+] Found factorization!'
                return (ZZ(p),N / ZZ(p))
                break
if __name__ == "__main__":

    d0 = 5238253532970779584300798844492170572461522036976648762627692667226340559020088694156157875799328715295731714152613342112215473678377358560145458174397208455979209727645223025461796934613732255293776878914793969645610207394668316208376575435
    e = 3
    N = 14548226081122368560032514119230156611256236693171817207357126022104950405215153274624566831564279036480211725192865596129638402390134492142004381271095441739828666191933227218882406337670431562810081114509911030182497172709311442888451607788434906044130025416355609818902478756914342327808346110015916448653312232449225768269460358320837334093393366001177062641910868097143718542435560064112106345757226225228529914503549173769542407620336661072716642280311702147374665184655269157358536267286675549837568584369012251122321382116325989605546301539720721082148162511285094832592834690141782230919002921619807888876027
    ct = 157173794341012649969896966530355628790995060260134002390201457734972386806088143712643909979231737460399900010219328725166144097135661064957290509895368127156401201390700517620947974793326363051059467321454627761356182437643617841364366868256345473870636483797271991968869
    known_bits = 800
    print NBITS(N)
    p,q = find_pq(d0,e,N)
    print 'p =', p
    print 'q =', q
    fn = (p-1)*(q-1)
    d = pow(e,-1,fn)
    m = pow(ct,d,N)
    m = ZZ(m)
    print 'm = ' ,m
    print hex(m)[2:].decode('hex')
    
